/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> result((0,0));
        if(!root)  return result;
        /*
        可在树的遍历过程中寻找合适路径，若已知路径总和加上目标节点刚好等于sum，则继续探索另一条路径直至全部探索完
        所有可能的路径。
        注意：本题路径需一直延伸至叶节点;本题需考虑到二叉树中有负数的情况
        */
        vector<int> resultTemp;  //用于记录探索路径
        findPath(root, result, resultTemp, 0, sum);
        return result;
    }

    //本题用vector result实现了一个栈的功能
    void findPath(TreeNode* pNode, vector<vector<int>>& result, vector<int>& resultTemp, int sumTemp, int sum){
        sumTemp += pNode->val;
        //找到一条路径(需到达叶节点)
        if(!pNode->left && !pNode->right){
            if(sumTemp == sum){
                resultTemp.push_back(pNode->val);
                result.push_back(resultTemp);
                resultTemp.pop_back();
            }
            return;
        }

        resultTemp.push_back(pNode->val);
        if(pNode->left)  findPath(pNode->left, result, resultTemp, sumTemp, sum);
        if(pNode->right)  findPath(pNode->right, result, resultTemp, sumTemp, sum);
        resultTemp.pop_back();

        return;
    }
};